/*
Copyleft (C) 2005 Hélio Perroni Filho
xperroni@yahoo.com
ICQ: 2490863

This file is part of ChatterBean.

ChatterBean is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

ChatterBean is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with ChatterBean (look at the Documents/ directory); if not, either write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA, or visit (http://www.gnu.org/licenses/gpl.txt).
*/

package bitoflife.chatterbean;

import bitoflife.chatterbean.aiml.Category;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Graphmaster {
  /*
  Attributes
  */

  /* The children of this node. */
  private final Map<String, Graphmaster> children = new HashMap<String, Graphmaster>();

  private int size = 0;
  private Graphmaster parent;
  private Category category;
  private String name; // The name of a node is the pattern element it represents.

  private Graphmaster(String name) {
    this.name = name;
  }

  /**
   * Constructs a new root node.
   */
  public Graphmaster() {
  }

  /**
   * Constructs a new tree, with this node as the root.
   */
  public Graphmaster(List<Category> categories) {
    append(categories);
  }

  /*
  Methods
  */

  private void append(Category category, String[] elements, int index) {
    Graphmaster child = children.get(elements[index]);
    if (child == null) {
      appendChild(child = new Graphmaster(elements[index]));
    }

    int nextIndex = index + 1;
    if (elements.length <= nextIndex) {
      child.category = category;
    } else {
      child.append(category, elements, nextIndex);
    }
  }

  private void appendChild(Graphmaster child) {
    children.put(child.name, child);
    child.parent = this;
  }

  /**
   * <p>
   * Returns an array with three child nodes, in the following order:
   * </p>
   * <ul>
   * <li>The "_" node;</li>
   * <li>The node with the given name;</li>
   * <li>The "*" node.</li>
   * </ul>
   * <p>
   * If any of these nodes can not be found among this node's children, its position is filled by <code>null</code>.
   * </p>
   */
  private Graphmaster[] children(String name) {
    return new Graphmaster[]{children.get("_"), children.get(name), children.get("*")};
  }


  /**
   * 是否是通配符
   *
   * @return
   */
  private boolean isWildcard() {
    return ("_".equals(name) || "*".equals(name));
  }


  private Category match(Match match, int index) {
    if (isWildcard()) {
      return matchWildcard(match, index);
    }

    if (!name.equals(match.getMatchPath(index))) {
      return null;
    }

    int nextIndex = index + 1;
    if (match.getMatchPathLength() <= nextIndex) {
      return category;
    }

    return matchChildren(match, nextIndex);
  }


  /**
   * 递归匹配
   *
   * @param match
   * @param nextIndex
   * @return
   */
  private Category matchChildren(Match match, int nextIndex) {
    Graphmaster[] nodes = children(match.getMatchPath(nextIndex));
    for (int i = 0, n = nodes.length; i < n; i++) {
      Category category = (nodes[i] != null ? nodes[i].match(match, nextIndex) : null);

      if (category != null) {
        return category;
      }
    }

    return null;
  }

  private Category matchWildcard(Match match, int index) {
    int n = match.getMatchPathLength();
    for (int i = index; i < n; i++) {
      Category category = matchChildren(match, i);
      if (category != null) {
        match.appendWildcard(index, i);
        return category;
      }
    }

    if (category != null) {
      match.appendWildcard(index, n);
    }
    return category;
  }

  public void append(List<Category> categories) {
    for (Category category : categories) {
      append(category);
    }
  }

  public void append(Category category) {
    String matchPath[] = category.getMatchPath();
    append(category, matchPath, 0);
    size++;
  }

  /**
   * 匹配Catgeory
   * <p>
   * Returns the Catgeory which Pattern matches the given Sentence, or <code>null</code> if it cannot be found.
   */
  public Category match(Match match) {
    return matchChildren(match, 0);
  }

  public int size() {
    return size;
  }
}
